package algorithm.dynamicProgramming.p198;

import java.util.Arrays;

/**
 * 198. 打家劫舍
 */
class Solution_v1 {
    private int[] memo;
    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return tryRob(nums, 0);
    }

    // 考虑抢劫nums[index...nums.size()]这个范围内的所有房子
    private int tryRob(int[] nums, int index) {
        if (index >= nums.length) {
            return 0;
        }

        if (memo[index] != -1) {
            return memo[index];
        }
        for (int i = index; i < nums.length; i++) {
            // 确定抢劫第 i 间房子
            memo[index] = Math.max(memo[index], nums[i] + tryRob(nums, i + 2));
        }

        return memo[index];
    }

    public static void main(String[] args) {
        System.out.println(new Solution_v1().rob(new int[]{2, 7, 9, 3, 1}));
    }
}